package com.major.dawn.leetCode.list;

public class MiddleNode {

//  头结点非空，确定链表的长度，我才能知道中间链表的位置
//    遍历链表，得到size ，确定中间位置，再去定位   O(n+n/2)
//    遍历链表，转成map或者数组  O(n)

//    前面两种方法的思路都很直接，不在尝试，主要是对第一种的尝试，快慢指针法
    public ListNode middleNode(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null ) {
            fast = fast.next;
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next;
            }
        }
        return slow;
    }
}
